JD13 完全数计算

本节目标：理解“JD13 完全数计算”的核心思路，并能把它用于实际开发或面试表达。 简单 通过率：51.54% 时间限制：1秒 空间限制：32M 描述 完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。 它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。 例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

输入n，请输出n以内(含n)完全数的个数。

数据范围： 1≤n≤5×105 输入描述： 输入一个数字n 输出描述： 输出不超过n的完全数的个数 示例1 输入： 1000 ==复制== 输出： 3

要找出不超过n的完全数的个数，我们可以对每一个数x（从1到n），检查它是否是完全数。判断一个数是否是完全数的方法是：找出它的所有真因子（即除了自身以外的约数），计算这些真因子的和，如果这个和等于原数，则它是完全数。

这个方法的时间复杂度较高，特别是对于较大的n值，但对于较小的n（如题目中的数据范围），这种方法是可行的。 def is_perfect_number(num):

计算一个数的所有真因子之和

sum_of_factors = sum([i for i in range(1, num) if num % i == 0])

如果真因子之和等于原数，则是完全数

return sum_of_factors == num

def count_perfect_numbers(n):

计算不超过n的完全数的个数

count = 0 for i in range(1, n + 1): if is_perfect_number(i): count += 1 return count

输入

n = int(input())

输出不超过n的完全数的个数

print(count_perfect_numbers(n))

优化方法

• 所有完美数都是偶数
• 大于这个数1/2的公因子是不存在的，第二次循环次数减少了一半
• 一个数的约数总是成对出现的，我们只要找平方根一侧的，别一侧的通过除法获得，如28，我们只找小于5的，找到4时，我们用28/4，得到7，这样减少遍历

def get_sum_of_proper_divisors(number): """计算并返回一个数的所有真因子之和。""" sum_of_divisors = 1 # 初始化为1，因为1是每个数的因子

遍历可能的因子，只需检查到该数的平方根

for possible_divisor in range(2, int(number ** 0.5) + 1): if number % possible_divisor == 0: paired_divisor = number // possible_divisor if possible_divisor == paired_divisor: # 因子是平方根的情况 sum_of_divisors += possible_divisor else: sum_of_divisors += possible_divisor + paired_divisor return sum_of_divisors

def count_perfect_numbers(up_to): """计算并返回不超过给定上限的完全数的数量。""" perfect_numbers = [] for num in range(2, up_to): if num == get_sum_of_proper_divisors(num): perfect_numbers.append(num) return len(perfect_numbers)

读取输入并打印结果

upper_limit = int(input()) print(count_perfect_numbers(upper_limit))

优化方法二 当数据范围较大时，逐个检查每个数是否为完美数的方法变得不可行，因为这种方法的时间复杂度较高。然而，鉴于完美数非常稀少，并且到目前为止已知的完美数都与梅森素数（Mersenne primes）紧密相关，我们可以利用这一性质来优化我们的算法。

到目前为止已知的所有完美数都是偶数，并且可以表示为2^(p-1) * (2^p - 1)的形式，其中2^p - 1是梅森素数。因此，我们只需要检查这种形式的数是否在我们的范围内，这样可以大大减少需要检查的数的数量。

由于数据范围n为1≤n≤5×10^5，我们只需要检查前几个梅森素数对应的完美数。目前已知的梅森素数对应的p值较小，例如2, 3, 5, 7, 13, 17, 19等。

下面是一个优化后的方法，它只检查这些特定形式的数：

def find_perfect_numbers(n):

已知的梅森素数的指数p

primes = [2, 3, 5, 7, 13, 17, 19, 31] perfect_numbers = [] # 检查每个梅森素数对应的完美数是否小于等于n for p in primes: perfect_number = (2 ** (p - 1)) * ((2 ** p) - 1) if perfect_number <= n: perfect_numbers.append(perfect_number) else: break return perfect_numbers

输入

n = int(input())

找到不超过n的所有完美数

perfect_numbers = find_perfect_numbers(n)

输出完美数的个数

print(len(perfect_numbers))

这段代码首先定义了一个包含已知梅森素数的指数p的列表。然后，它计算每个这样的p对应的完美数，并检查这些完美数是否不超过输入的n。如果一个完美数小于等于n，就将它添加到结果列表中。最后，输出不超过n的完美数的个数。

这种方法只检查少量特定的数，因此比逐个检查每个数是否为完美数的方法快得多，并且可以满足题目中对时间和空间的限制要求。